package hot100;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/10/17 9:42
 */
public class lc32最长有效括号 {

    public static void main(String[] args) {
        String s = "()(())";
        System.out.println(longestValidParentheses(s));
    }
    public static int longestValidParentheses(String s) {
        int ans = 0,len = s.length();

        int dp[] = new int[len + 1];
        // dp[i] 表示 以 i 开头到 结尾的 有效括号的长度， 不能直接 一步把状态方程定义到位？  dp[i]： 表示 以i开头到结尾的 **最长** 有效括号？
        // 还是 **子串**  和 **子序列的** 区别？
        // ())) ((()))  通过这个 字符串就能明白差不多了
        // s[i] = ')' 开头是无效的， 必须是 以‘（’ 开头 才可能是有效的
        for (int i = len - 2; i>=0  ; i--) {
            if(s.charAt(i) == '('){
                if(s.charAt(i + 1) == ')'){
                    dp[i] = dp[i + 2] + 2;
                }else if(dp[i + 1] > 0){
                    int latter = i + dp[i + 1] + 1;
                    if(latter < len && s.charAt(latter) == ')'){
                        dp[i] =  dp[i + 1] + 2 + (latter + 1 <= len ? dp[latter + 1] : 0);
                    }
                }
            }
            ans = Math.max(ans,dp[i]);
        }
        System.out.println(Arrays.toString(dp));
        return ans;
    }


}
